home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 46 / Amiga Format CD46 (1999-10-20)(Future Publishing)(GB)[!][issue 1999-12].iso / -serious- / comms / www / urlx / ubi_bintree.c < prev    next >
C/C++ Source or Header  |  1999-09-06  |  43KB  |  1,034 lines
  1. /* ========================================================================== **
  2.  *                              ubi_BinTree.c
  3.  *
  4.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  5.  *
  6.  *  Email:  crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *
  9.  *  ubi_BinTree manages a simple binary tree.  Nothing fancy here.  No height
  10.  *  balancing, no restructuring.  Still, a good tool for creating short, low-
  11.  *  overhead sorted lists of things that need to be found in a hurry.
  12.  *
  13.  *  In addition, this module provides a good basis for creating other types
  14.  *  of binary tree handling modules.
  15.  *
  16.  * -------------------------------------------------------------------------- **
  17.  *
  18.  *  This library is free software; you can redistribute it and/or
  19.  *  modify it under the terms of the GNU Library General Public
  20.  *  License as published by the Free Software Foundation; either
  21.  *  version 2 of the License, or (at your option) any later version.
  22.  *
  23.  *  This library is distributed in the hope that it will be useful,
  24.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26.  *  Library General Public License for more details.
  27.  *
  28.  *  You should have received a copy of the GNU Library General Public
  29.  *  License along with this library; if not, write to the Free
  30.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31.  *
  32.  * -------------------------------------------------------------------------- **
  33.  *
  34.  * $Log: ubi_BinTree.c,v $
  35.  * Revision 2.4  1997/07/26 04:11:10  crh
  36.  * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
  37.  *   and ubi_trFALSE.
  38.  * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
  39.  * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
  40.  * + Added function ubi_btLeafNode().
  41.  *
  42.  * Revision 2.3  1997/06/03 05:16:17  crh
  43.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
  44.  * Also changed the interface to function InitTree().  See the comments
  45.  * for this function for more information.
  46.  *
  47.  * Revision 2.2  1995/10/03 22:00:07  CRH
  48.  * Ubisized!
  49.  * 
  50.  * Revision 2.1  95/03/09  23:37:10  CRH
  51.  * Added the ModuleID static string and function.  These modules are now
  52.  * self-identifying.
  53.  * 
  54.  * Revision 2.0  95/02/27  22:00:17  CRH
  55.  * Revision 2.0 of this program includes the following changes:
  56.  *
  57.  *     1)  A fix to a major typo in the RepaceNode() function.
  58.  *     2)  The addition of the static function Border().
  59.  *     3)  The addition of the public functions FirstOf() and LastOf(), which
  60.  *         use Border(). These functions are used with trees that allow
  61.  *         duplicate keys.
  62.  *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
  63.  *         a "comparison" operator.
  64.  *     5)  Overall enhancements to both code and comments.
  65.  *
  66.  * I decided to give this a new major rev number because the interface has
  67.  * changed.  In particular, there are two new functions, and changes to the
  68.  * Locate() function.
  69.  *
  70.  * Revision 1.0  93/10/15  22:44:59  CRH
  71.  * With this revision, I have added a set of #define's that provide a single,
  72.  * standard API to all existing tree modules.  Until now, each of the three
  73.  * existing modules had a different function and typedef prefix, as follows:
  74.  *
  75.  *       Module        Prefix
  76.  *     ubi_BinTree     ubi_bt
  77.  *     ubi_AVLtree     ubi_avl
  78.  *     ubi_SplayTree   ubi_spt
  79.  *
  80.  * To further complicate matters, only those portions of the base module
  81.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  82.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  83.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  84.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  85.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  86.  *
  87.  * This was not too terrible if you were familiar with the modules and knew
  88.  * exactly which tree model you wanted to use.  If you wanted to be able to
  89.  * change modules (for speed comparisons, etc), things could get messy very
  90.  * quickly.
  91.  *
  92.  * So, I have added a set of defined names that get redefined in any of the
  93.  * descendant modules.  To use this standardized interface in your code,
  94.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  95.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  96.  * datatype names for the module that you are using.  Just remember to
  97.  * include the header for that module in your program file.  Because these
  98.  * names are handled by the preprocessor, there is no added run-time
  99.  * overhead.
  100.  *
  101.  * Note that the original names do still exist, and can be used if you wish
  102.  * to write code directly to a specific module.  This should probably only be
  103.  * done if you are planning to implement a new descendant type, such as
  104.  * red/black trees.  CRH
  105.  *
  106.  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  107.  *
  108.  * ========================================================================== **
  109.  */
  110.  
  111. #include "ubi_BinTree.h"            /* Header for this module          */
  112. #include <stdlib.h>                 /* Standard C definitions.         */
  113.  
  114. /* ========================================================================== **
  115.  * Static data.
  116.  */
  117.  
  118. static char ModuleID[] = "ubi_BinTree\n\
  119. \t$Revision: 2.4 $\n\
  120. \t$Date: 1997/07/26 04:11:10 $\n\
  121. \t$Author: crh $\n";
  122.  
  123. /* ========================================================================== **
  124.  * Internal (private) functions.
  125.  */
  126.  
  127. static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
  128.                             ubi_btItemPtr  FindMe,
  129.                    register ubi_btNodePtr  p )
  130.   /* ------------------------------------------------------------------------ **
  131.    * This function performs a non-recursive search of a tree for a node
  132.    * matching a specific key.  It is called "qFind()" because it is
  133.    * faster that TreeFind (below).
  134.    *
  135.    *  Input:
  136.    *     cmp      -  a pointer to the tree's comparison function.
  137.    *     FindMe   -  a pointer to the key value for which to search.
  138.    *     p        -  a pointer to the starting point of the search.  <p>
  139.    *                 is considered to be the root of a subtree, and only
  140.    *                 the subtree will be searched.
  141.    *
  142.    *  Output:
  143.    *     A pointer to a node with a key that matches the key indicated by
  144.    *     FindMe, or NULL if no such node was found.
  145.    *
  146.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  147.    *          not* point to the (sequentially) first occurance of the
  148.    *          desired key.
  149.    * ------------------------------------------------------------------------ **
  150.    */
  151.   {
  152.   char tmp;
  153.  
  154.   while( p && (( tmp = AbNormal((*cmp)(FindMe, p)) ) != EQUAL) )
  155.     p = p->Link[tmp];
  156.  
  157.   return( p );
  158.   } /* qFind */
  159.  
  160. static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
  161.                                ubi_btNodePtr  p,
  162.                                ubi_btNodePtr *parentp,
  163.                                char          *gender,
  164.                                ubi_btCompFunc CmpFunc )
  165.   /* ------------------------------------------------------------------------ **
  166.    * TreeFind() searches a tree for a given value (findme).  It will return a
  167.    * pointer to the target node, if found, or NULL if the target node was not
  168.    * found.
  169.    *
  170.    * TreeFind() also returns, via parameters, a pointer to the parent of the
  171.    * target node, and a LEFT or RIGHT value indicating which child of the
  172.    * parent is the target node.  *If the target is not found*, then these
  173.    * values indicate the place at which the target *should be found*.  This
  174.    * is useful when inserting a new node into a tree or searching for nodes
  175.    * "near" the target node.
  176.    *
  177.    * The parameters are:
  178.    *
  179.    *  findme   -  is a pointer to the key information to be searched for.
  180.    *  p        -  points to the root of the tree to be searched.
  181.    *  parentp  -  will return a pointer to a pointer to the !parent! of the
  182.    *              target node, which can be especially usefull if the target
  183.    *              was not found.
  184.    *  gender   -  returns LEFT or RIGHT to indicate which child of *parentp
  185.    *              was last searched.
  186.    *  CmpFunc  -  points to the comparison function.
  187.    *
  188.    * This function is called by ubi_btLocate() and ubi_btInsert().
  189.    * ------------------------------------------------------------------------ **
  190.    */
  191.   {
  192.   register ubi_btNodePtr tmp_p = p;
  193.   ubi_btNodePtr tmp_pp = NULL;
  194.   char tmp_sex = EQUAL;
  195.   char tmp_cmp;
  196.  
  197.   while( tmp_p && (EQUAL != (tmp_cmp = AbNormal((*CmpFunc)(findme, tmp_p)))) )
  198.     {
  199.     tmp_pp  = tmp_p;                /* Keep track of previous node. */
  200.     tmp_sex = tmp_cmp;              /* Keep track of sex of child.  */
  201.     tmp_p = tmp_p->Link[tmp_cmp];   /* Go to child. */
  202.     }
  203.   *parentp = tmp_pp;                /* Return results. */
  204.   *gender  = tmp_sex;
  205.   return( tmp_p );
  206.   } /* TreeFind */
  207.  
  208. static void ReplaceNode( ubi_btNodePtr *parent,
  209.                          ubi_btNodePtr  oldnode,
  210.                          ubi_btNodePtr  newnode )
  211.   /* ------------------------------------------------------------------ *
  212.    * Remove node oldnode from the tree, replacing it with node newnode.
  213.    *
  214.    * Input:
  215.    *  parent   - A pointer to he parent pointer of the node to be
  216.    *             replaced.  <parent> may point to the Link[] field of
  217.    *             a parent node, or it may indicate the root pointer at
  218.    *             the top of the tree.
  219.    *  oldnode  - A pointer to the node that is to be replaced.
  220.    *  newnode  - A pointer to the node that is to be installed in the
  221.    *             place of <*oldnode>.
  222.    *
  223.    * Notes:    Don't forget to free oldnode.
  224.    *           Also, this function used to have a really nasty typo
  225.    *           bug.  "oldnode" and "newnode" were swapped in the line
  226.    *           that now reads:
  227.    *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  228.    *           Bleah!
  229.    * ------------------------------------------------------------------ *
  230.    */
  231.   {
  232.   register int i;
  233.   register int btNodeSize = sizeof( ubi_btNode );
  234.  
  235.   for( i = 0; i < btNodeSize; i++ ) /* Copy node internals to new node. */
  236.     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  237.   (*parent) = newnode;              /* Old node's parent points to new child. */
  238.   /* Now tell the children about their new step-parent. */
  239.   if( oldnode->Link[LEFT ] ) (oldnode->Link[LEFT ])->Link[PARENT] = newnode;
  240.   if( oldnode->Link[RIGHT] ) (oldnode->Link[RIGHT])->Link[PARENT] = newnode;
  241.   } /* ReplaceNode */
  242.  
  243. static void SwapNodes( ubi_btRootPtr RootPtr,
  244.                        ubi_btNodePtr Node1,
  245.                        ubi_btNodePtr Node2 )
  246.   /* ------------------------------------------------------------------------ **
  247.    * This function swaps two nodes in the tree.  Node1 will take the place of
  248.    * Node2, and Node2 will fill in the space left vacant by Node 1.
  249.    *
  250.    * Input:
  251.    *  RootPtr  - pointer to the tree header structure for this tree.
  252.    *  Node1    - \
  253.    *              > These are the two nodes which are to be swapped.
  254.    *  Node2    - /
  255.    *
  256.    * Notes:
  257.    *  This function does a three step swap, using a dummy node as a place
  258.    *  holder.  This function is used by ubi_btRemove().
  259.    * ------------------------------------------------------------------------ **
  260.    */
  261.   {
  262.   ubi_btNodePtr *Parent;
  263.   ubi_btNode     dummy;
  264.   ubi_btNodePtr  dummy_p = &dummy;
  265.  
  266.   /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
  267.   if( Node1->Link[PARENT] )
  268.     Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
  269.   else
  270.     Parent = &(RootPtr->root);
  271.   ReplaceNode( Parent, Node1, dummy_p );
  272.  
  273.   /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */
  274.   if( Node2->Link[PARENT] )
  275.     Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
  276.   else
  277.     Parent = &(RootPtr->root);
  278.   ReplaceNode( Parent, Node2, Node1 );
  279.  
  280.   /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */
  281.   if( dummy_p->Link[PARENT] )
  282.     Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
  283.   else
  284.     Parent = &(RootPtr->root);
  285.   ReplaceNode( Parent, dummy_p, Node2 );
  286.   } /* SwapNodes */
  287.  
  288. /* -------------------------------------------------------------------------- **
  289.  * These routines allow you to walk through the tree, forwards or backwards.
  290.  */
  291.  
  292. static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
  293.                                register char  whichway )
  294.   /* ------------------------------------------------------------------------ **
  295.    * Slide down the side of a subtree.
  296.    *
  297.    * Given a starting node, this function returns a pointer to the LEFT-, or
  298.    * RIGHT-most descendent, *or* (if whichway is PARENT) to the tree root.
  299.    *
  300.    *  Input:  P         - a pointer to a starting place.
  301.    *          whichway  - the direction (LEFT, RIGHT, or PARENT) in which to
  302.    *                      travel.
  303.    *  Output: A pointer to a node that is either the root, or has no
  304.    *          whichway-th child but is within the subtree of P.  Note that
  305.    *          the return value may be the same as P.  The return value *will
  306.    *          be* NULL if P is NULL.
  307.    * ------------------------------------------------------------------------ **
  308.    */
  309.   {
  310.   ubi_btNodePtr Q = NULL;
  311.  
  312.   while( P )
  313.     {
  314.     Q = P;
  315.     P = P->Link[ whichway ];
  316.     }
  317.   return( Q );
  318.   } /* SubSlide */
  319.  
  320. static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
  321.                                register char  whichway )
  322.   /* ------------------------------------------------------------------------ **
  323.    * Given starting point p, return the (key order) next or preceeding node
  324.    * in the tree.
  325.    *
  326.    *  Input:  P         - Pointer to our starting place node.
  327.    *          whichway  - the direction in which to travel to find the
  328.    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
  329.    *                      neighbor.
  330.    *
  331.    *  Output: A pointer to the neighboring node, or NULL if P was NULL.
  332.    *
  333.    *  Notes:  If whichway is PARENT, the results are unpredictable.
  334.    * ------------------------------------------------------------------------ **
  335.    */
  336.   {
  337.   if( P )
  338.     {
  339.     if( P->Link[ whichway ] )
  340.       return( SubSlide( P->Link[ whichway ], (char)RevWay(whichway) ) );
  341.     else
  342.       while( P->Link[ PARENT ] )
  343.         {
  344.         if( (P->Link[ PARENT ])->Link[ whichway ] == P )
  345.           P = P->Link[ PARENT ];
  346.         else
  347.           return( P->Link[ PARENT ] );
  348.         }
  349.     }
  350.   return( NULL );
  351.   } /* Neighbor */
  352.  
  353. static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
  354.                              ubi_btItemPtr FindMe,
  355.                              ubi_btNodePtr p,
  356.                              char          whichway )
  357.   /* ------------------------------------------------------------------------ **
  358.    * Given starting point p, which has a key value equal to *FindMe, locate
  359.    * the first (index order) node with the same key value.
  360.    *
  361.    * This function is useful in trees that have can have duplicate keys.
  362.    * For example, consider the following tree:
  363.    *     Tree                                                      Traversal
  364.    *       2    If <p> points to the root and <whichway> is RIGHT,     3
  365.    *      / \    then the return value will be a pointer to the       / \
  366.    *     2   2    RIGHT child of the root node.  The tree on         2   5
  367.    *    /   / \    the right shows the order of traversal.          /   / \
  368.    *   1   2   3                                                   1   4   6
  369.    *
  370.    *  Input:  RootPtr   - Pointer to the tree root structure.
  371.    *          FindMe    - Key value for comparisons.
  372.    *          p         - Pointer to the starting-point node.
  373.    *          whichway  - the direction in which to travel to find the
  374.    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
  375.    *                      neighbor.
  376.    *
  377.    *  Output: A pointer to the first (index, or "traversal", order) node with
  378.    *          a Key value that matches *FindMe.
  379.    *
  380.    *  Notes:  If whichway is PARENT, or if the tree does not allow duplicate
  381.    *          keys, this function will return <p>.
  382.    * ------------------------------------------------------------------------ **
  383.    */
  384.   {
  385.   register ubi_btNodePtr q;
  386.  
  387.   /* Exit if there's nothing that can be done. */
  388.   if( !Dups_OK( RootPtr ) || (PARENT == whichway) )
  389.     return( p );
  390.  
  391.   /* First, if needed, move up the tree.  We need to get to the root of the
  392.    * subtree that contains all of the matching nodes.
  393.    */
  394.   q = p->Link[PARENT];
  395.   while( q && (EQUAL == AbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
  396.     {
  397.     p = q;
  398.     q = p->Link[PARENT];
  399.     }
  400.  
  401.   /* Next, move back down in the "whichway" direction. */
  402.   q = p->Link[whichway];
  403.   while( q )
  404.     {
  405.     if( q = qFind( RootPtr->cmp, FindMe, q ) )
  406.       {
  407.       p = q;
  408.       q = p->Link[whichway];
  409.       }
  410.     }
  411.   return( p );
  412.   } /* Border */
  413.  
  414.  
  415. /* ========================================================================== **
  416.  * Exported utilities.
  417.  */
  418.  
  419. long ubi_btSgn( register long x )
  420.   /* ------------------------------------------------------------------------ **
  421.    * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
  422.    *
  423.    *  Input:  x - a signed long integer value.
  424.    *
  425.    *  Output: the "sign" of x, represented as follows:
  426.    *            -1 == negative
  427.    *             0 == zero (no sign)
  428.    *             1 == positive
  429.    *
  430.    * Note: This utility is provided in order to facilitate the conversion
  431.    *       of C comparison function return values into BinTree direction
  432.    *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
  433.    *       AbNormal() conversion macro!
  434.    *
  435.    * ------------------------------------------------------------------------ **
  436.    */
  437.   {
  438.   return( (x)?((x>0)?(1):(-1)):(0) );
  439.   } /* ubi_btSgn */
  440.  
  441. ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
  442.   /* ------------------------------------------------------------------------ **
  443.    * Initialize a tree node.
  444.    *
  445.    *  Input:  a pointer to a ubi_btNode structure to be initialized.
  446.    *  Output: a pointer to the initialized ubi_btNode structure (ie. the
  447.    *          same as the input pointer).
  448.    * ------------------------------------------------------------------------ **
  449.    */
  450.   {
  451.   NodePtr->Link[ LEFT ]   = NULL;
  452.   NodePtr->Link[ PARENT ] = NULL;
  453.   NodePtr->Link[ RIGHT ]  = NULL;
  454.   NodePtr->gender         = EQUAL;
  455.   return( NodePtr );
  456.   } /* ubi_btInitNode */
  457.  
  458. ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr   RootPtr,
  459.                               ubi_btCompFunc  CompFunc,
  460.                               unsigned char   Flags )
  461.   /* ------------------------------------------------------------------------ **
  462.    * Initialize the fields of a Tree Root header structure.
  463.    *
  464.    *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
  465.    *                       initialized.
  466.    *           CompFunc  - a pointer to a comparison function that will be used
  467.    *                       whenever nodes in the tree must be compared against
  468.    *                       outside values.
  469.    *           Flags     - One bytes worth of flags.  Flags include
  470.    *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
  471.    *                       file for more info.
  472.    *
  473.    *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
  474.    *           same value as RootPtr).
  475.    *
  476.    *  Note:    The interface to this function has changed from that of
  477.    *           previous versions.  The <Flags> parameter replaces two
  478.    *           boolean parameters that had the same basic effect.
  479.    *
  480.    * ------------------------------------------------------------------------ **
  481.    */
  482.   {
  483.   if( RootPtr )
  484.     {
  485.     RootPtr->root   = NULL;
  486.     RootPtr->count  = 0L;
  487.     RootPtr->cmp    = CompFunc;
  488.     RootPtr->flags  = (Flags & ubi_trDUPKEY) ? ubi_trDUPKEY : Flags;
  489.     }                 /* There are only two supported flags, and they are
  490.                        * mutually exclusive.  ubi_trDUPKEY takes precedence
  491.                        * over ubi_trOVERWRITE.
  492.                        */
  493.   return( RootPtr );
  494.   } /* ubi_btInitTree */
  495.  
  496. ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
  497.                          ubi_btNodePtr  NewNode,
  498.                          ubi_btItemPtr  ItemPtr,
  499.                          ubi_btNodePtr *OldNode )
  500.   /* ------------------------------------------------------------------------ **
  501.    * This function uses a non-recursive algorithm to add a new element to the
  502.    * tree.
  503.    *
  504.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  505.    *                       the root of the tree to which NewNode is to be added.
  506.    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
  507.    *                       part of any tree.
  508.    *           ItemPtr  -  A pointer to the sort key that is stored within
  509.    *                       *NewNode.  ItemPtr MUST point to information stored
  510.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  511.    *                       indicated by ItemPtr is used to place the new node
  512.    *                       into the tree.
  513.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  514.    *                       the tree, a duplicate node may be found.  If
  515.    *                       duplicates are allowed, then the new node will
  516.    *                       be simply placed into the tree.  If duplicates
  517.    *                       are not allowed, however, then one of two things
  518.    *                       may happen.
  519.    *                       1) if overwritting *is not* allowed, this
  520.    *                          function will return FALSE (indicating that
  521.    *                          the new node could not be inserted), and
  522.    *                          *OldNode will point to the duplicate that is
  523.    *                          still in the tree.
  524.    *                       2) if overwritting *is* allowed, then this
  525.    *                          function will swap **OldNode for *NewNode.
  526.    *                          In this case, *OldNode will point to the node
  527.    *                          that was removed (thus allowing you to free
  528.    *                          the node).
  529.    *                          **  If you are using overwrite mode, ALWAYS  **
  530.    *                          ** check the return value of this parameter! **
  531.    *                 Note: You may pass NULL in this parameter, the
  532.    *                       function knows how to cope.  If you do this,
  533.    *                       however, there will be no way to return a
  534.    *                       pointer to an old (ie. replaced) node (which is
  535.    *                       a problem if you are using overwrite mode).
  536.    *
  537.    *  Output:  a boolean value indicating success or failure.  The function
  538.    *           will return FALSE if the node could not be added to the tree.
  539.    *           Such failure will only occur if duplicates are not allowed,
  540.    *           nodes cannot be overwritten, AND a duplicate key was found
  541.    *           within the tree.
  542.    * ------------------------------------------------------------------------ **
  543.    */
  544.   {
  545.   ubi_btNodePtr OtherP,
  546.                 parent = NULL;
  547.   char          tmp;
  548.  
  549.   if( !(OldNode) )       /* If they didn't give us a pointer, supply our own. */
  550.     OldNode = &OtherP;
  551.  
  552.   (void)ubi_btInitNode( NewNode );     /* Init the new node's BinTree fields. */
  553.  
  554.   /* Find a place for the new node. */
  555.   *OldNode = TreeFind(ItemPtr, (RootPtr->root), &parent, &tmp, (RootPtr->cmp));
  556.  
  557.   /* Now add the node to the tree... */
  558.   if (!(*OldNode)) /* The easy one: we have a space for a new node! */
  559.     {
  560.     if (!(parent))
  561.       RootPtr->root = NewNode;
  562.     else
  563.       {
  564.       parent->Link[tmp]     = NewNode;
  565.       NewNode->Link[PARENT] = parent;
  566.       NewNode->gender       = tmp;
  567.       }
  568.     (RootPtr->count)++;
  569.     return( ubi_trTRUE );
  570.     }
  571.  
  572.   /* If we reach this point, we know that a duplicate node exists.  This
  573.    * section adds the node to the tree if duplicate keys are allowed.
  574.    */
  575.   if( Dups_OK(RootPtr) )    /* Key exists, add duplicate */
  576.     {
  577.     ubi_btNodePtr q;
  578.  
  579.     tmp = RIGHT;
  580.     q = (*OldNode);
  581.     *OldNode = NULL;
  582.     while( q )
  583.       {
  584.       parent = q;
  585.       if( tmp == EQUAL ) tmp = RIGHT;
  586.       q = q->Link[tmp];
  587.       if ( q )
  588.         tmp = AbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
  589.       }
  590.     parent->Link[tmp]      = NewNode;
  591.     NewNode->Link[PARENT]  = parent;
  592.     NewNode->gender        = tmp;
  593.     (RootPtr->count)++;
  594.     return( ubi_trTRUE );
  595.     }
  596.  
  597.   /* If we get to *this* point, we know that we are not allowed to have
  598.    * duplicate nodes, but our node keys match, so... may we replace the
  599.    * old one?
  600.    */
  601.   if( Ovwt_OK(RootPtr) )    /* Key exists, we replace */
  602.     {
  603.     if (!(parent))
  604.       ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
  605.     else
  606.       ReplaceNode( &(parent->Link[(*OldNode)->gender]), *OldNode, NewNode );
  607.     return( ubi_trTRUE );
  608.     }
  609.  
  610.   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
  611.   } /* ubi_btInsert */
  612.  
  613. ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
  614.                             ubi_btNodePtr DeadNode )
  615.   /* ------------------------------------------------------------------------ **
  616.    * This function removes the indicated node from the tree.
  617.    *
  618.    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
  619.    *                       the node to be removed.
  620.    *           DeadNode -  A pointer to the node that will be removed.
  621.    *
  622.    *  Output:  This function returns a pointer to the node that was removed
  623.    *           from the tree (ie. the same as DeadNode).
  624.    *
  625.    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
  626.    *           strange and evil things will happen to your trees.
  627.    * ------------------------------------------------------------------------ **
  628.    */
  629.   {
  630.   ubi_btNodePtr p,
  631.                *parentp;
  632.   char          tmp;
  633.  
  634.   /* if the node has both left and right subtrees, then we have to swap
  635.    * it with another node.  The other node we choose will be the Prev()ious
  636.    * node, which is garunteed to have no RIGHT child.
  637.    */
  638.   if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
  639.     SwapNodes( RootPtr, DeadNode, ubi_btPrev( DeadNode ) );
  640.  
  641.   /* The parent of the node to be deleted may be another node, or it may be
  642.    * the root of the tree.  Since we're not sure, it's best just to have
  643.    * a pointer to the parent pointer, whatever it is.
  644.    */
  645.   if (DeadNode->Link[PARENT])
  646.     parentp = &((DeadNode->Link[PARENT])->Link[DeadNode->gender]);
  647.   else
  648.     parentp = &( RootPtr->root );
  649.  
  650.   /* Now link the parent to the only grand-child and patch up the gender. */
  651.   tmp = ((DeadNode->Link[LEFT])?LEFT:RIGHT);
  652.  
  653.   p = (DeadNode->Link[tmp]);
  654.   if( p )
  655.     {
  656.     p->Link[PARENT] = DeadNode->Link[PARENT];
  657.     p->gender       = DeadNode->gender;
  658.     }
  659.   (*parentp) = p;
  660.  
  661.   /* Finished, reduce the node count and return. */
  662.   (RootPtr->count)--;
  663.   return( DeadNode );
  664.   } /* ubi_btRemove */
  665.  
  666. ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
  667.                             ubi_btItemPtr FindMe,
  668.                             ubi_trCompOps CompOp )
  669.   /* ------------------------------------------------------------------------ **
  670.    * The purpose of ubi_btLocate() is to find a node or set of nodes given
  671.    * a target value and a "comparison operator".  The Locate() function is
  672.    * more flexible and (in the case of trees that may contain dupicate keys)
  673.    * more precise than the ubi_btFind() function.  The latter is faster,
  674.    * but it only searches for exact matches and, if the tree contains
  675.    * duplicates, Find() may return a pointer to any one of the duplicate-
  676.    * keyed records.
  677.    *
  678.    *  Input:
  679.    *     RootPtr  -  A pointer to the header of the tree to be searched.
  680.    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
  681.    *                 search.
  682.    *     CompOp   -  One of the following:
  683.    *                    CompOp     Return a pointer to the node with
  684.    *                    ------     ---------------------------------
  685.    *                   ubi_trLT - the last key value that is less
  686.    *                              than FindMe.
  687.    *                   ubi_trLE - the first key matching FindMe, or
  688.    *                              the last key that is less than
  689.    *                              FindMe.
  690.    *                   ubi_trEQ - the first key matching FindMe.
  691.    *                   ubi_trGE - the first key matching FindMe, or the
  692.    *                              first key greater than FindMe.
  693.    *                   ubi_trGT - the first key greater than FindMe.
  694.    *  Output:
  695.    *     A pointer to the node matching the criteria listed above under
  696.    *     CompOp, or NULL if no node matched the criteria.
  697.    *
  698.    *  Notes:
  699.    *     In the case of trees with duplicate keys, Locate() will behave as
  700.    *     follows:
  701.    *
  702.    *     Find:  3                       Find: 3
  703.    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
  704.    *                  ^ ^         ^                   ^ ^
  705.    *                 LT EQ        GT                 LE GE
  706.    *
  707.    *     That is, when returning a pointer to a node with a key that is LESS
  708.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  709.    *     LAST matching node.
  710.    *     When returning a pointer to a node with a key that is GREATER
  711.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  712.    *     FIRST matching node.
  713.    *
  714.    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
  715.    * ------------------------------------------------------------------------ **
  716.    */
  717.   {
  718.   register ubi_btNodePtr p;
  719.   ubi_btNodePtr   parent;
  720.   char            whichkid;
  721.  
  722.   /* Start by searching for a matching node. */
  723.   p = TreeFind( FindMe,
  724.                 RootPtr->root,
  725.                 &parent,
  726.                 &whichkid,
  727.                 RootPtr->cmp );
  728.  
  729.   if( p )   /* If we have found a match, we can resolve as follows: */
  730.     {
  731.     switch( CompOp )
  732.       {
  733.       case ubi_trLT:            /* It's just a jump to the left...  */
  734.         p = Border( RootPtr, FindMe, p, LEFT );
  735.         return( Neighbor( p, LEFT ) );
  736.       case ubi_trGT:            /* ...and then a jump to the right. */
  737.         p = Border( RootPtr, FindMe, p, RIGHT );
  738.         return( Neighbor( p, RIGHT ) );
  739.       }
  740.     p = Border( RootPtr, FindMe, p, LEFT );
  741.     return( p );
  742.     }
  743.  
  744.   /* Else, no match. */
  745.   if( ubi_trEQ == CompOp )    /* If we were looking for an exact match... */
  746.     return( NULL );           /* ...forget it.                            */
  747.  
  748.   /* We can still return a valid result for GT, GE, LE, and LT.
  749.    * <parent> points to a node with a value that is either just before or
  750.    * just after the target value.
  751.    * Remaining possibilities are LT and GT (including LE & GE).
  752.    */
  753.   if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
  754.     return( (LEFT  == whichkid) ? Neighbor( parent, whichkid ) : parent );
  755.   else
  756.     return( (RIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
  757.   } /* ubi_btLocate */
  758.  
  759. ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
  760.                           ubi_btItemPtr FindMe )
  761.   /* ------------------------------------------------------------------------ **
  762.    * This function performs a non-recursive search of a tree for any node
  763.    * matching a specific key.
  764.    *
  765.    *  Input:
  766.    *     RootPtr  -  a pointer to the header of the tree to be searched.
  767.    *     FindMe   -  a pointer to the key value for which to search.
  768.    *
  769.    *  Output:
  770.    *     A pointer to a node with a key that matches the key indicated by
  771.    *     FindMe, or NULL if no such node was found.
  772.    *
  773.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  774.    *          not* point to the (sequentially) first occurance of the
  775.    *          desired key.  In such a tree, it may be more useful to use
  776.    *          ubi_btLocate().
  777.    * ------------------------------------------------------------------------ **
  778.    */
  779.   {
  780.   return( qFind( RootPtr->cmp, FindMe, RootPtr->root ) );
  781.   } /* ubi_btFind */
  782.  
  783. ubi_btNodePtr ubi_btNext( ubi_btNodePtr P )
  784.   /* ------------------------------------------------------------------------ **
  785.    * Given the node indicated by P, find the (sorted order) Next node in the
  786.    * tree.
  787.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  788.    *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
  789.    *           to the "last" node in the tree or was NULL.
  790.    * ------------------------------------------------------------------------ **
  791.    */
  792.   {
  793.   return( Neighbor( P, RIGHT ) );
  794.   } /* ubi_btNext */
  795.  
  796. ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
  797.   /* ------------------------------------------------------------------------ **
  798.    * Given the node indicated by P, find the (sorted order) Previous node in
  799.    * the tree.
  800.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  801.    *  Output:  A pointer to the "previous" node in the tree, or NULL if P
  802.    *           pointed to the "first" node in the tree or was NULL.
  803.    * ------------------------------------------------------------------------ **
  804.    */
  805.   {
  806.   return( Neighbor( P, LEFT ) );
  807.   } /* ubi_btPrev */
  808.  
  809. ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
  810.   /* ------------------------------------------------------------------------ **
  811.    * Given the node indicated by P, find the (sorted order) First node in the
  812.    * subtree of which *P is the root.
  813.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  814.    *  Output:  A pointer to the "first" node in a subtree that has *P as its
  815.    *           root.  This function will return NULL only if P is NULL.
  816.    *  Note:    In general, you will be passing in the value of the root field
  817.    *           of an ubi_btRoot structure.
  818.    * ------------------------------------------------------------------------ **
  819.    */
  820.   {
  821.   return( SubSlide( P, LEFT ) );
  822.   } /* ubi_btFirst */
  823.  
  824. ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
  825.   /* ------------------------------------------------------------------------ **
  826.    * Given the node indicated by P, find the (sorted order) Last node in the
  827.    * subtree of which *P is the root.
  828.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  829.    *  Output:  A pointer to the "last" node in a subtree that has *P as its
  830.    *           root.  This function will return NULL only if P is NULL.
  831.    *  Note:    In general, you will be passing in the value of the root field
  832.    *           of an ubi_btRoot structure.
  833.    * ------------------------------------------------------------------------ **
  834.    */
  835.   {
  836.   return( SubSlide( P, RIGHT ) );
  837.   } /* ubi_btLast */
  838.  
  839. ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
  840.                              ubi_btItemPtr MatchMe,
  841.                              ubi_btNodePtr p )
  842.   /* ------------------------------------------------------------------------ **
  843.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  844.    * the tree, this function will return a pointer to the first (traversal
  845.    * order) node with the same key value.
  846.    *
  847.    *  Input:  RootPtr - A pointer to the root of the tree.
  848.    *          MatchMe - A pointer to the key value.  This should probably
  849.    *                    point to the key within node *p.
  850.    *          p       - A pointer to a node in the tree.
  851.    *  Output: A pointer to the first node in the set of nodes with keys
  852.    *          matching <FindMe>.
  853.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  854.    *          <FindMe>.  If not, this function will return NULL.
  855.    * ------------------------------------------------------------------------ **
  856.    */
  857.   {
  858.   /* If our starting point is invalid, return NULL. */
  859.   if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
  860.     return( NULL );
  861.   return( Border( RootPtr, MatchMe, p, LEFT ) );
  862.   } /* ubi_btFirstOf */
  863.  
  864. ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
  865.                             ubi_btItemPtr MatchMe,
  866.                             ubi_btNodePtr p )
  867.   /* ------------------------------------------------------------------------ **
  868.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  869.    * the tree, this function will return a pointer to the last (traversal
  870.    * order) node with the same key value.
  871.    *
  872.    *  Input:  RootPtr - A pointer to the root of the tree.
  873.    *          MatchMe - A pointer to the key value.  This should probably
  874.    *                    point to the key within node *p.
  875.    *          p       - A pointer to a node in the tree.
  876.    *  Output: A pointer to the last node in the set of nodes with keys
  877.    *          matching <FindMe>.
  878.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  879.    *          <FindMe>.  If not, this function will return NULL.
  880.    * ------------------------------------------------------------------------ **
  881.    */
  882.   {
  883.   /* If our starting point is invalid, return NULL. */
  884.   if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
  885.     return( NULL );
  886.   return( Border( RootPtr, MatchMe, p, RIGHT ) );
  887.   } /* ubi_btLastOf */
  888.  
  889. ubi_trBool ubi_btTraverse( ubi_btRootPtr   RootPtr,
  890.                            ubi_btActionRtn EachNode,
  891.                            void           *UserData )
  892.   /* ------------------------------------------------------------------------ **
  893.    * Traverse a tree in sorted order (non-recursively).  At each node, call
  894.    * (*EachNode)(), passing a pointer to the current node, and UserData as the
  895.    * second parameter.
  896.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  897.    *                       the tree to be traversed.
  898.    *           EachNode -  a pointer to a function to be called at each node
  899.    *                       as the node is visited.
  900.    *           UserData -  a generic pointer that may point to anything that
  901.    *                       you choose.
  902.    *  Output:  A boolean value.  FALSE if the tree is empty, otherwise TRUE.
  903.    * ------------------------------------------------------------------------ **
  904.    */
  905.   {
  906.   ubi_btNodePtr p;
  907.  
  908.   if( !(p = ubi_btFirst( RootPtr->root )) ) return( ubi_trFALSE );
  909.  
  910.   while( p )
  911.     {
  912.     EachNode( p, UserData );
  913.     p = ubi_btNext( p );
  914.     }
  915.   return( ubi_trTRUE );
  916.   } /* ubi_btTraverse */
  917.  
  918. ubi_trBool ubi_btKillTree( ubi_btRootPtr     RootPtr,
  919.                            ubi_btKillNodeRtn FreeNode )
  920.   /* ------------------------------------------------------------------------ **
  921.    * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
  922.    * structure.  Note that this function will return FALSE if either parameter
  923.    * is NULL.
  924.    *
  925.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  926.    *                       the root of the tree to delete.
  927.    *           FreeNode -  a function that will be called for each node in the
  928.    *                       tree to deallocate the memory used by the node.
  929.    *
  930.    *  Output:  A boolean value.  FALSE if either input parameter was NULL, else
  931.    *           TRUE.
  932.    *
  933.    * ------------------------------------------------------------------------ **
  934.    */
  935.   {
  936.   ubi_btNodePtr p, q;
  937.  
  938.   if( !(RootPtr) || !(FreeNode) )
  939.     return( ubi_trFALSE );
  940.  
  941.   p = ubi_btFirst( RootPtr->root );
  942.   while( p )
  943.     {
  944.     q = p;
  945.     while( q->Link[RIGHT] )
  946.       q = SubSlide( q->Link[RIGHT], LEFT );
  947.     p = q->Link[PARENT];
  948.     if( p )
  949.       p->Link[ ((p->Link[LEFT] == q)?LEFT:RIGHT) ] = NULL;
  950.     FreeNode((void *)q);
  951.     }
  952.  
  953.   (void)ubi_btInitTree( RootPtr,
  954.                         RootPtr->cmp,
  955.                         RootPtr->flags );
  956.   return( ubi_trTRUE );
  957.   } /* ubi_btKillTree */
  958.  
  959. ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
  960.   /* ------------------------------------------------------------------------ **
  961.    * Returns a pointer to a leaf node.
  962.    *
  963.    *  Input:  leader  - Pointer to a node at which to start the descent.
  964.    *
  965.    *  Output: A pointer to a leaf node selected in a somewhat arbitrary
  966.    *          manner.
  967.    *
  968.    *  Notes:  I wrote this function because I was using splay trees as a
  969.    *          database cache.  The cache had a maximum size on it, and I
  970.    *          needed a way of choosing a node to sacrifice if the cache
  971.    *          became full.  In a splay tree, less recently accessed nodes
  972.    *          tend toward the bottom of the tree, meaning that leaf nodes
  973.    *          are good candidates for removal.  (I really can't think of
  974.    *          any other reason to use this function.)
  975.    *        + In a simple binary tree or an AVL tree, the most recently
  976.    *          added nodes tend to be nearer the bottom, making this a *bad*
  977.    *          way to choose which node to remove from the cache.
  978.    *        + Randomizing the traversal order is probably a good idea.  You
  979.    *          can improve the randomization of leaf node selection by passing
  980.    *          in pointers to nodes other than the root node each time.  A
  981.    *          pointer to any node in the tree will do.  Of course, if you
  982.    *          pass a pointer to a leaf node you'll get the same thing back.
  983.    *
  984.    * ------------------------------------------------------------------------ **
  985.    */
  986.   {
  987.   ubi_btNodePtr follower = NULL;
  988.   int           whichway = LEFT;
  989.  
  990.   while( NULL != leader )
  991.     {
  992.     follower = leader;
  993.     leader   = follower->Link[ whichway ];
  994.     if( NULL == leader )
  995.       {
  996.       whichway = RevWay( whichway );
  997.       leader   = follower->Link[ whichway ];
  998.       }
  999.     }
  1000.  
  1001.   return( follower );
  1002.   } /* ubi_btLeafNode */
  1003.  
  1004. int ubi_btModuleID( int size, char *list[] )
  1005.   /* ------------------------------------------------------------------------ **
  1006.    * Returns a set of strings that identify the module.
  1007.    *
  1008.    *  Input:  size  - The number of elements in the array <list>.
  1009.    *          list  - An array of pointers of type (char *).  This array
  1010.    *                  should, initially, be empty.  This function will fill
  1011.    *                  in the array with pointers to strings.
  1012.    *  Output: The number of elements of <list> that were used.  If this value
  1013.    *          is less than <size>, the values of the remaining elements are
  1014.    *          not guaranteed.
  1015.    *
  1016.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  1017.    *          stored in static memory.  Don't free() them, don't write over
  1018.    *          them, etc.  Just read them.
  1019.    * ------------------------------------------------------------------------ **
  1020.    */
  1021.   {
  1022.   if( size > 0 )
  1023.     {
  1024.     list[0] = ModuleID;
  1025.     if( size > 1 )
  1026.       list[1] = NULL;
  1027.     return( 1 );
  1028.     }
  1029.   return( 0 );
  1030.   } /* ubi_btModuleID */
  1031.  
  1032.  
  1033. /* ========================================================================== */
  1034.